/*
https://leetcode.cn/problems/filling-bookcase-shelves/solution/dong-tai-gui-hua-python3-by-smoon1989/
 */
public class Solution1105 {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int[] f=new int[books.length+1];
        for (int i=0;i<books.length;i++){
            f[i+1]=f[i]+books[i][1];
            int t=books[i][0];
            int m=i-1;
            int maxH=books[i][1];
            while (m>=0){
                t+=books[m][0];
                if (t>shelfWidth){
                    break;
                }
                maxH=Math.max(maxH,books[m][1]);
                f[i+1]=Math.min(f[i+1],f[m]+maxH);
                m--;
            }
        }
        return f[books.length];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1105().minHeightShelves(new int[][]{{1,1},{2,3},{2,3},{1,1},{1,1},{1,1},{1,2}},4));
    }
}
